/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		vector<TreeNode*> q;
		dfs(root, q);

		TreeNode* first = NULL;
		TreeNode* second = NULL;

		int n = q.size();
		for (int i = 0; i + 1 < n; ++i) {
			if (!first) {
				if (q[i]->val > q[i + 1]->val) {
					first = q[i];
					second = q[i + 1];
				}
			} else {
				if (q[i]->val > q[i + 1]->val) {
					second = q[i + 1];
					break;
				}
			}
		}
		swap(first->val, second->val);
    }

	void dfs(TreeNode* root, vector<TreeNode*>& q) {
		if (root == NULL) {
			return;
		}
		if (root->left) {
			dfs(root->left, q);
		}
		q.push_back(root);
		if (root->right) {
			dfs(root->right, q);
		}
	}
};